package cn.fansunion.leecode.math;

/**
 * 605. 种花问题 <br/>假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。<br/>
 * 可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。<br/>
 * 
 * 给你一个整数数组  flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。<br/>
 * 
 * 另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？<br/>
 * 
 * 能则返回 true ，不能则返回 false。
 * 
 * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/can-place-flowers 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 
 * @author wen.lei@brgroup.com
 *
 *         2022-2-26
 */
public class CanPlaceFlowers {
    /*  示例 1：
    
    输入：flowerbed = [1,0,0,0,1], n = 1
    输出：true
    示例 2：
    
    输入：flowerbed = [1,0,0,0,1], n = 2
    输出：false
     
    
    提示：
    
    1 <= flowerbed.length <= 2 * 104
    flowerbed[i] 为 0 或 1
    flowerbed 中不存在相邻的两朵花
    0 <= n <= flowerbed.length*/
    /**
     * 方法1：严格按照题目的要求，逐步种花，统计能够种花的数量m。return: m>=n
     * error：没能通过全部用例，数组的边界值
     * 问题：能种花时，改变了数组，测试用例传进来的数组不能重复使用了
     * @param flowerbed
     * @param n
     * @return
     */
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int m = 0;
        for (int index = 0; index < flowerbed.length; index++) {
            // 当前元素为1时，说明已经有花了，因此只考虑为0的情况
            // 核心规则：当前元素的左中右，全都为0时，才能种花
            boolean currentCan = flowerbed[index] == 0;
            boolean leftCan = true;
            boolean rightCan = true;
            //边界值经常出问题额，>=0，不是>0
            if (index - 1 >= 0) {
                leftCan = flowerbed[index - 1] == 0;
            }
            if (index + 1 < flowerbed.length) {
                rightCan = flowerbed[index + 1] == 0;
            }
            if (leftCan && currentCan && rightCan) {
                m++;
                //为了方便，改变了数组
                flowerbed[index] = 1;
            }
        }
        final boolean can = m >= n;
        return can;
    }
    
    /**
     * 方法2 error：根据规律，题目蕴含的信息和技巧：找出数组n最多1的个数 maxSum，当前1的个数currentSum <br/>
     * return:(maxSum-currentSum)>=n，然后还需要考虑到特殊情况: 奇数时，maxSum不是稳定的，受到第0+1个“是否种花了”的影响<br/>
     * (观察有误：受到正中间“是否种花了”的影响)
     * 另外一个好处：本方法，不改变数组
     * error：此方法有瑕疵，不能适用所有的情况，发现的规律不够通用
     * @param flowerbed
     * @param n
     * @return
     */
    public boolean canPlaceFlowerError(int[] flowerbed, int n) {
        //不种花，肯定行
        if(n==0) {
            return true;
        }
        //超过最大值，肯定不行
        if(n > flowerbed.length / 2+1) {
            return false;
        }
        // 当前1的个数
        int currentSum = currentSum(flowerbed);
        // 最大1的个数，奇数时最大为n/2+1；偶数时，最大为n/2
        // 最小1的个数，是不稳定的
        // [1];
        // [1,0],[0,1];[1,0,1],[0,1,0],[0,0,1]，3时，最大为2，最小为1；[1,0,1,0],[0,1,0,1],[0,0,1,0],[0,0,0,1]；[1,0,1,0,1],[0,1,0,1,0];
        // 5时，[1,0,1,0,1],[0,1,0,1,0]，最大为3，最小为2
        // [1,0,1,0,1,0,1],[0,1,0,1,0,1,0] 7时，最大为4，最小为3
        int maxSum = 0;
        // 偶数时，最大能种数是固定的(此观察错误了：1有的在奇数位，有的在偶数位，没出现1次，就会导致出现连续的2个0、0，多了之后，就浪费了1个盆)
        if (flowerbed.length % 2 == 0) {
            maxSum = flowerbed.length / 2;
        } else {
            // 奇数时，根据第1个花的位置，maxSum比偶数时的maxSum少1个
            boolean firstOneEvenCanPlusOne = firstOneEvenCanPlusOne(flowerbed);
            if (firstOneEvenCanPlusOne) {
                //奇数个数且第1个1在偶数位，可以多种1个
                //坑：数组的第0个，算偶数位
                //坑2：如果数组中没有1，也能多种1个，也算“偶数位”
                maxSum = flowerbed.length / 2+1;
            } else {
                maxSum = flowerbed.length / 2;
            }
        }
        return (maxSum - currentSum) >= n;

    }

    /**
     *  第1个花的位置index，是否为偶数。如果不存在1，默认为奇数。奇数时，比在偶数时，能种的花多1个
     * @param flowerbed
     * @return
     */
    private boolean firstOneEvenCanPlusOne(int[] flowerbed) {
        int firstOneIndex=-1;
        for (int index = 0; index < flowerbed.length; index++) {
            //发现第1个“花”
            if (flowerbed[index] == 1) {
                firstOneIndex=index;
            }
        }
        if(firstOneIndex==-1) {
            return true;
        }
        return firstOneIndex%2==0;
    }

    private int currentSum(int[] flowerbed) {
        int sum = 0;
        for (int i : flowerbed) {
            if (i == 1) {
                sum++;
            }
        }
        return sum;
    }
    
   
}
